<?php
class HashTable
{
    protected $table=[];
    protected $table_size=100;
    protected $count=0;
    protected function hash($item)
    {
        $bit0=$item%10;
        $bit1=($item%100-$item%10)/10;
        $bit2=($item%1000-$item%100)/100;
        $value=$item-pow(7,$bit0)-pow(3,$bit1)+pow(11,$bit2)+$bit0+$bit1+$bit2;
        $value = $value>0 ? $value : -$value; 
        return $value%($this->table_size);
    }
    protected function rehash()
    {
        $old_table=$this->table;
        $old_size=$this->table_size;
        $old_count=$this->count;
        $this->table=[];
        $this->table_size=$old_size*2;
        $this->count=0;
        for($i=0;$i<$old_size;$i++){
            if(isset($old_table[$i])){
                foreach($old_table[$i] as $item){
                    $this->insert($item);
                }
            }
        }
    }
    public function insert($item)
    {
        $hash=$this->hash($item);
        if(isset($this->table[$hash])){
            $this->table[$hash][]=$item;
        }
        else{
            $this->table[$hash]=[$item];
        }
        $this->count++;
        if($this->count*2 > $this->table_size){
            $this->rehash();
        }
    }
    public function remove()
    {

    }
    public function find($item)
    {
        $hash=$this->hash($item);
        if(isset($this->table[$hash])){
            return $hash;
        }
        else{
            return false;
        }
    }
    public function update()
    {

    }
    /**
     * 合并另一个哈希表
     * @param self $table
     */
    public function merge($table)
    {

    }
    public function output()
    {
        $str="";
        for($i=0;$i<$this->table_size;$i++){
            $str.="$i-\t";
            if(isset($this->table[$i])){
                $str.=implode(",",$this->table[$i]);
            }
            $str.="\r\n";
        }
        return $str;
    }
}